A transformation of considerable importance for signal processing is the discrete Fourier transform (DFT). It may be calculated using the chirp-Z transform (CZT) algorithm, a method which is suitable for implementation via acoustic surface wave devices as well as other forms of the transversal filter. The CZT algorithm decomposes the DFT into a premultiplication by a discrete chirp, a convolution with a discrete chirp, and a postmultiplication by a discrete chirp.
This is illustrated in FIG. 4 and by the following equations for an N-point DFT: ##EQU1## but, EQU -2 mn=-m.sup.2 +(m-n).sup.2 -n.sup.2 ; (2)
as may be seen by expanding the right side of the equation.
Therefore, ##EQU2##
Since this algorithm requires the use of complex numbers, its implementation with real hardware requires the use of four convolvers. The real and imaginary components of the input signal g.sub.n are multiplied by the real and imaginary components of the premultiplier chirp, e.sup.-jn.spsp.2.sup./N, as indicated by the two factors in the parenthesis of Eq. (3), and combined in pairs to drive the inputs of four chirp convolvers. The convolution is expressed by the terms including and to the right of the summation sign .SIGMA.. The convolver outputs are combined in pairs and multiplied by the real and imaginary components of the postmultiplier chirp, e.sup.-j.pi.m.spsp.2.sup./N, and combined again to provide the real and imaginary components of the output G.sub.m.
The computation time of the device is proportional to the number of samples, N, in the time signal. If N is a power of 2 the computation time of the Fast Fourier Transform (FFT) is N log.sub.2 N. This device is thus a factor of log.sub.2 N faster than a FFT device using one complex multiplier of the same speed.
The background information hereinabove is derived from an article entitled "Real Time Discrete Fourier Transforms Using Surface Acoustic Wave Devices", by J. M. Alsup, et al, which appeared in the Proc. IEE International Specialists Seminar on Component Performance and System Applications of Surface Acoustic Wave Devices, Aviemore, Scotland, U.D., September 25-27, 1973.
Two other articles provide useful background information. One is entitled "Surface Acoustic Wave CZT Processors", by J. M. Alsup, which appears in the 1974 Ultrasonics Symposium Proceedings, IEEE Cat. No. 74 CHO 896-1SU. The other article is entitled "Frequency Synthesis via the Discrete Chirp and Prime Sequence ROM's", by James M. Alsup, et al which appeared in the Proceedings of the IEEE, Vol. 64, May 1976.